#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

typedef int Position;
typedef struct LNode *List;
struct LNode {
    int Data[MAXSIZE];
    Position Last;
};

Position BinarySearch(List, int, Position, Position);

int main()
{
    int i = 0, numberToFind, numberPosition;
    List L;
    L = (List)malloc(sizeof(struct LNode));
    printf("Ints number: ");
    scanf(" %d", &L->Last);
    printf("Input numbers: ");
    while (i < L->Last) 
        scanf(" %d", &L->Data[i++]);

    printf("Input the number to find: ");
    scanf("%d", &numberToFind);

    numberPosition = BinarySearch(L, numberToFind, 0, L->Last - 1);
    if (numberPosition > -1)
        printf("The number position is %d", numberPosition + 1);
    else
        printf("Can not find %d", numberToFind);

    return 0;
}

Position BinarySearch(List L, int X, Position Left, Position Right)
{
    if (Right < Left) 
        return -1;
    
    Position Mid = (Left + Right) / 2;
    if (L->Data[Mid] > X)
        return BinarySearch(L, X, Left, Mid - 1);
    else if (L->Data[Mid] < X)
        return BinarySearch(L, X, Mid + 1, Right);
    else
        return Mid;
}